package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC786 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] kthSmallestPrimeFraction(int[] arr, int k) {
            int n = arr.length;
            PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
                double i1 = arr[a[0]] * 1.0 / arr[a[1]], i2 = arr[b[0]] * 1.0 / arr[b[1]];
                return Double.compare(i1, i2);
            });
            for (int i = 1; i < n; i++) q.add(new int[]{0, i});
            while (k-- > 1) {
                int[] poll = q.poll();
                int i = poll[0], j = poll[1];
                if (i + 1 < j) q.add(new int[]{i + 1, j});
            }
            int[] poll = q.poll();
            return new int[]{arr[poll[0]], arr[poll[1]]};
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC786 an = new LC786();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
